package oj;

import java.util.Scanner;

public class KY11 {
    //内部类来存储节点值、左树、右树
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
        public static void main(String[] args){
            Scanner scanner=new Scanner(System.in);
            while(scanner.hasNext()){
                //line中存储的是字符串形式的二叉树
                String line=scanner.next();
                //str->TreeNode
                TreeNode root=build(line);
                //中序遍历二叉树，并按照格式打印
                inOrder(root);
                //每个结果占一行
                System.out.println();
            }
        }

        //根据先序遍历结果的字符串还原二叉树，并返回还原后的根节点
        private static TreeNode build(String line){
            return preOrderBuild(line);
        }


//abc##de#g##f###
     static int index=0;
     private static TreeNode preOrderBuild(String line) {
         char c = line.charAt(index);
         if(c=='#'){
             return null;
         }
         //根节点
            TreeNode root = new TreeNode(c);
         //继续处理下一个字符
            index++;
            //继续处理左子树
            root.left=build(line);
            index++;
            //继续处理右子树
            root.right=build(line);
        return root;
    }

    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
        }
    }
